import java.util.Deque;
import java.util.LinkedList;

public class Repetition_Sort {
    //冒泡排序
    /*
    时间复杂度：O(n^2)
    空间复杂度: O(1)
     */
    public  void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j+1,j);
                    flag=true;
                }
            }
            if(!flag) return ;
        }
    }

// 快速排序 未优化 递归
    //挖坑法
    /*
    时间复杂度：最坏请况下：O(n^2);
              最好情况下：O(n*logn)
    空间复杂度：最坏：O(n)
              最好：O(logn)
     */
//    public  void quickSort(int[] array){
//        quickNor(array,0,array.length-1);
//    }
//
//    private void quickNor(int[] arr,int left,int right){
//        if(left>=right) return ;
//            int index = quick( arr, left, right) ;
//
//            quickNor(arr,left,index-1);
//            quickNor(arr,index+1,right);
//    }
//
//    private  int quick(int[] arr,int left,int right){
//        int tmp =arr[left];
//        while(left<right){
//            for (;right>left;right--){
//                if(arr[right]<tmp){
//                    arr[left]=arr[right];
//                    break;
//                }
//            }
//            for (;right>left;left++){
//                if (arr[left]>tmp){
//                    arr[right]=arr[left];
//                    break;
//                }
//            }
//        }
//        arr[left]=tmp;
//        return left;
//    }


    //快速排序 挖坑法 优化版 递归
    public static void quickSort(int[] array){
        quickNor(array,0,array.length-1);
    }

    private static void quickNor(int[] arr,int left,int right){
        if(left>=right) return ;

        int mid = (left+right)/2;
        quickTmp(arr,left,mid,right);

        int index = quick( arr, left, right) ;

        quickNor(arr,left,index-1);
        quickNor(arr,index+1,right);
    }

    private static int quick(int[] arr,int left,int right){
        int tmp =arr[left];
        while(left<right){
            for (;right>left;right--){
                if(arr[right]<tmp){
                    arr[left]=arr[right];
                    break;
                }
            }
            for (;right>left;left++){
                if (arr[left]>tmp){
                    arr[right]=arr[left];
                    break;
                }
            }
        }
        arr[left]=tmp;
        return left;
    }

    private static int quickTmp(int[] arr,int left,int mid,int right){
        if(arr[left]>arr[right]){
            if (arr[mid]>arr[left]) return arr[left];
            else if (arr[right]>arr[mid]) return arr[right];
            else return arr[mid];
        }else {
            if(arr[mid]<arr[left]) return arr[left];
            else if (arr[mid]>arr[right]) return arr[right];
            else return arr[mid];
        }
    }

    //快速排序  非递归实现
    public static void quickSort2(int[] arr){
        quickNor2(arr,0,arr.length-1);
    }
    private static void quickNor2(int[] arr,int left,int right){
        int pivot = quick(arr,0,arr.length-1);
        Deque<Integer> deque = new LinkedList<>();

        if(pivot>left+1){
            deque.push(left);
            deque.push(pivot-1);
        }
        if(pivot<right-1){
            deque.push(pivot+1);
            deque.push(right);
        }
        while(!deque.isEmpty()){
            right=deque.poll();
            left=deque.poll();
            pivot = quick(arr, left, right);

            if(pivot>left+1){
                deque.push(left);
                deque.push(pivot-1);
            }
            if(pivot<right-1){
                deque.push(pivot+1);
                deque.push(right);
            }
        }
    }


    public int[] selectSort(int[] arr){
        int left = 0;
        int right = arr.length-1;
        while(left<right){
            int minIndex = left;
            int maxIndex = left;
            for (int i=left+1;i<=right;i++){
                if(arr[i]<arr[minIndex]){
                    minIndex = i;
                }
                if(arr[i]>arr[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(arr,left,minIndex);
            if (maxIndex==left) maxIndex = minIndex;
            swap(arr,right,maxIndex);
            right--;
            left++;

        }
        return arr;
    }

    public int[] heapSort(int arr[]){
        if (arr==null) return null;
        createHeap(arr);
        return arr;
    }

    private void createHeap(int[] arr){
        for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
            shiftDown(arr,i,arr.length);
        }
        small_To_Big(arr);
    }

    private void shiftDown(int[] arr,int parent,int length){
        int child = 2*parent+1;
        while(child<length){
            if (child+1<length&&arr[child]<arr[child+1]){
                child++;
            }
            if (arr[child]>arr[parent]){
                swap(arr,child,parent);
            }
            else break;
            parent=child;
            child=2*parent+1;
        }
    }

    private void small_To_Big(int[] arr){
        int end = arr.length-1;
        while(end>0) {
            swap(arr,0,end);
            shiftDown(arr,0,end--);
        }
    }

    private void swap(int[] arr,int index1,int index2){
        int tmp = arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=tmp;
    }

    // 归并排序---递归
    /*
    时间复杂度：O(N*logn)
    空间复杂度：O(n)
     */
     public static void mergeSort1(int[] array){
        mergeSortTmp(array,0,array.length-1);
    }

    private static void mergeSortTmp(int[] array, int left, int right) {
        if(left>=right) return ;
        int mid = (left+right)/2;
        mergeSortTmp(array,left,mid);
        mergeSortTmp(array,mid+1,right);

        merge(array,left,mid,right);
    }

    private static void merge(int[] array, int left,int mid, int right) {
        int s1 = left;
//        int ei = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] arr = new int[right-left+1];
        int i=0;
        while(s1<=mid&&s2<=e2){
            if(array[s1]<array[s2]){
                arr[i]=array[s1];
                s1++;
                i++;
            }else {
                arr[i]=array[s2];
                s2++;
                i++;
            }
        }
        while(s1<=mid){ //s1=0  mid =0
            if (s1<=mid){
                arr[i]=array[s1];
                s1++;
                i++;
            }

        }
        while(s2<=e2){//s2=1  e2=1
            if (s2<=e2){
                arr[i]=array[s2];
                s2++;
                i++;
            }
        }
        for (int j = left; j <= right; j++) {
            array[j] = arr[j-left];
        }
    }

    // 归并排序---非递/*
    /*
    时间复杂度：O(n*logn)
    空间复杂度：O(n)
     */
     public static void mergeSort2(int[] array){
         int gap=1;
         while(gap<array.length){
             for(int i=0;i<array.length;i+=gap*2){
                 int mid = i+gap-1;
                 if(mid>=array.length){
                     mid=array.length-1;
                 }
                 int e1 = mid+gap;
                 if(e1>=array.length){
                     e1=array.length-1;
                 }
                 merge(array,i,mid,e1);
             }
             gap*=2;
         }
    }

// 计数排序
    /*
    时间复杂度：O(n+范围)
    空间复杂度：O(范围)
     */
     public static void countSort(int[] array){
         int min = array[0];
         int max = array[0];
         for (int i = 1; i < array.length; i++) {
             if(min>array[i]){
                 min=array[i];
             }
             if (max<array[i]){
                 max=i;
             }
         }
         int len = max-min+1;
         int[] arr =new int[len];
         for (int j = 0; j < array.length; j++) {
             int k=array[j]-min;
             arr[k]++;
         }
         int count=0;
         for (int i = 0; i < len; i++) {
             for (int j = arr[i]; j >0 ; j--) {
                 array[count]=i+min;
                 count++;
             }
         }
    }
}
